{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Key Distribution Kata\n",
    "\n",
    "**Key Distribution** quantum kata is a series of exercises designed to get you familiar with \n",
    "the BB84 protocol for quantum key distribution. This protocol allows two parties, Alice and Bob, to share a random secret key. \n",
    "\n",
    "* You can find a description of the BB84 protocol [here](https://en.wikipedia.org/wiki/BB84).\n",
    "* [Short animated video introducing BB84 protocol](https://www.youtube.com/watch?v=UVzRbU6y7Ks).\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl/⌘+Enter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin, first prepare this notebook for execution (if you skip this step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.10.1911.1607"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Preparation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Diagonal polarization\n",
    "\n",
    "**Input:** $N$ qubits (stored in an array of length $N$). Each qubit is either in $|0\\rangle$ or in $|1\\rangle$ state.\n",
    "\n",
    "**Goal:**  Convert the qubits to diagonal polarization: \n",
    "* if `qs[i]` was in state $|0\\rangle$, it should be transformed to $|+\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$,\n",
    "* if `qs[i]` was in state $|1\\rangle$, it should be transformed to $|-\\rangle = \\frac{1}{\\sqrt2}(|0\\rangle - |1\\rangle)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_DiagonalPolarization_Test\n",
    "\n",
    "operation DiagonalPolarization (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Equal superposition\n",
    " \n",
    "**Input**: A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "**Goal**:  Change the qubit state to a superposition state that has equal probabilities of measuring 0 and 1. \n",
    "\n",
    "> Note that this is not the same as keeping the qubit in the $|0\\rangle$ state with 50% probability and converting it to the $|1\\rangle$ state with 50% probability!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_EqualSuperposition_Test \n",
    "\n",
    "operation EqualSuperposition (q : Qubit) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. BB84 Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Generate random array\n",
    "\n",
    "**Input:** An integer $N$.\n",
    "\n",
    "**Output** :  A `Bool` array of length N, where each element is chosen at random. \n",
    "\n",
    "> This will be used by both Alice and Bob to choose either the sequence of bits to send or the sequence of bases (`false` indicates $|0\\rangle$ / $|1\\rangle$ basis, and `true` indicates $|+\\rangle$ / $|-\\rangle$ basis) to use when encoding/measuring the bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_RandomArray_Test \n",
    "\n",
    "operation RandomArray (N : Int) : Bool[] {\n",
    "    // ...\n",
    "    return new Bool[N];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Prepare Alice's qubits\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. `qs`: an array of $N$ qubits in the $|0\\rangle$ states,\n",
    "2. `bases`: a `Bool` array of length $N$; \n",
    "    `bases[i]` indicates the basis to prepare the i-th qubit in:  \n",
    "    * `false`: use $|0\\rangle$ / $|1\\rangle$ (computational) basis,\n",
    "    * `true`: use $|+\\rangle$ / $|-\\rangle$ (Hadamard/diagonal) basis.\n",
    "3. `bits`: a `Bool` array of length $N$;\n",
    "    `bits[i]` indicates the bit to encode in the i-th qubit: `false` = 0, `true` = 1.\n",
    "\n",
    "**Goal:**  Prepare the qubits in the described state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_PrepareAlicesQubits_Test\n",
    "\n",
    "operation PrepareAlicesQubits (qs : Qubit[], bases : Bool[], bits : Bool[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Measure Bob's qubits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. `qs`: an array of $N$ qubits;  \n",
    "   each qubit is in one of the following states: $|0\\rangle$, $|1\\rangle$, $|+\\rangle$, $|-\\rangle$. \n",
    "2. `bases`: a `Bool` array of length $N$; \n",
    "   `bases[i]` indicates the basis used to prepare the i-th qubit:\n",
    "   * `false`: $|0\\rangle$ / $|1\\rangle$ (computational) basis,\n",
    "   * `true`: $|+\\rangle$ / $|-\\rangle$ (Hadamard/diagonal) basis.\n",
    "\n",
    "**Output:** Measure each qubit in the corresponding basis and return an array of results \n",
    "(encoding measurement result `Zero` as `false` and `One` as `true`). \n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_MeasureBobsQubits_Test\n",
    "\n",
    "operation MeasureBobsQubits (qs : Qubit[], bases : Bool[]) : Bool[] {\n",
    "    // ...\n",
    "    return new Bool[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Generate the shared key!\n",
    "    \n",
    "**Inputs:**\n",
    "\n",
    "1. `basesAlice` and `basesBob`: `Bool` arrays of length $N$\n",
    "   describing Alice's and Bobs's choice of bases, respectively;\n",
    "2. `measurementsBob`: a `Bool` array of length $N$ describing Bob's measurement results.\n",
    "    \n",
    "**Output:** a `Bool` array representing the shared key generated by the protocol.\n",
    "\n",
    "> Note that you don't need to know both Alice's and Bob's bits to figure out the shared key!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_GenerateSharedKey_Test\n",
    "\n",
    "function GenerateSharedKey (basesAlice : Bool[], basesBob : Bool[], measurementsBob : Bool[]) : Bool[] {\n",
    "    // ...\n",
    "    return new Bool[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. Was communication secure?\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. `keyAlice` and `keyBob`: `Bool` arrays of equal length $N$ describing \n",
    "   the versions of the shared key obtained by Alice and Bob, respectively.\n",
    "2. `threshold`: an integer between 50 and 100 - the percentage of the key bits that have to match.\n",
    "    \n",
    "**Output:** `true` if the percentage of matching bits is greater than or equal to the threshold, and `false` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_CheckKeysMatch_Test\n",
    "\n",
    "function CheckKeysMatch (keyAlice : Bool[], keyBob : Bool[], threshold : Int) : Bool {\n",
    "    // The following lines enforce the constraints on the input that you are given.\n",
    "    // You don't need to modify them. Feel free to remove them, this won't cause your code to fail.\n",
    "    Fact(Length(keyAlice) == Length(keyBob), \"Input arrays should have the same length\");\n",
    "\n",
    "    // ...\n",
    "    return false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.6. Putting it all together\n",
    "\n",
    "**Goal:** Implement the entire BB84 protocol using tasks 2.1 - 2.5 \n",
    "and following the comments in the operation template. \n",
    "\n",
    "> This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the `Run_BB84Protocol` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_BB84Protocol`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_BB84Protocol () : Unit {\n",
    "    // 1. Alice chooses a random set of bits to encode in her qubits \n",
    "    //    and a random set of bases to prepare her qubits in.\n",
    "    // ...\n",
    "\n",
    "    // 2. Alice allocates qubits, encodes them using her choices and sends them to Bob.\n",
    "    //    (Note that you can not reflect \"sending the qubits to Bob\" in Q#)\n",
    "    // ...\n",
    "\n",
    "    // 3. Bob chooses a random set of bases to measure Alice's qubits in.\n",
    "    // ...\n",
    "\n",
    "    // 4. Bob measures Alice's qubits in his chosen bases.\n",
    "    // ...\n",
    "\n",
    "    // 5. Alice and Bob compare their chosen bases and use the bits in the matching positions to create a shared key.\n",
    "    // ...\n",
    "\n",
    "    // 6. Alice and Bob check to make sure nobody eavesdropped by comparing a subset of their keys\n",
    "    //    and verifying that more than a certain percentage of the bits match.\n",
    "    // For this step, you can check the percentage of matching bits using the entire key \n",
    "    // (in practice only a subset of indices is chosen to minimize the number of discarded bits).\n",
    "    // ...\n",
    "\n",
    "    // If you've done everything correctly, the generated keys will always match, since there is no eavesdropping going on.\n",
    "    // In the next section you will explore the effects introduced by eavesdropping.\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_BB84Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Eavesdropping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1. Eavesdrop!\n",
    "\n",
    "In this task you will try to implement an eavesdropper, Eve. \n",
    "\n",
    "Eve will intercept a qubit from the quantum channel that Alice and Bob are using. \n",
    "She will measure it in either the $|0\\rangle$ / $|1\\rangle$ basis or the $|+\\rangle$ / $|-\\rangle$ basis,\n",
    "reconstruct the qubit into the original state and send it back to the channel. \n",
    "Eve hopes that if she properly reconstructs the qubit after measurement she won't be caught!\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. `q`: a qubit in one of the following states: $|0\\rangle$, $|1\\rangle$, $|+\\rangle$, $|-\\rangle$.\n",
    "2. `basis`: Eve's guess of the basis she should use for measuring.\n",
    "   Recall that `false` indicates $|0\\rangle$ / $|1\\rangle$ basis and `true` indicates $|+\\rangle$ / $|-\\rangle$ basis. \n",
    "\n",
    "**Output:** the bit encoded in the qubit (`false` for $|0\\rangle$ / $|+\\rangle$ states, `true` for $|1\\rangle$ / $|-\\rangle$ states).\n",
    "\n",
    "In this task you are guaranteed that the basis you're given matches the one\n",
    "in which the qubit is encoded, that is, if you are given a qubit in state\n",
    "$|0\\rangle$ or $|1\\rangle$, you will be given `basis = false`, and if you are given a qubit in state\n",
    "$|+\\rangle$ or $|-\\rangle$, you will be given `basis = true`. This is different from a real\n",
    "eavesdropping scenario, in which you have to guess the basis yourself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_Eavesdrop_Test\n",
    "\n",
    "operation Eavesdrop (q : Qubit, basis : Bool) : Bool {\n",
    "    // ...\n",
    "    return false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.2. Catch the eavesdropper\n",
    "\n",
    "Add an eavesdropper into the BB84 protocol from task 2.6. \n",
    "\n",
    "Note that now we should be able to detect Eve and therefore we have to discard some of our keys!\n",
    "\n",
    "> Similar to task 2.6, this is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the `Run_BB84ProtocolWithEavesdropper` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_BB84ProtocolWithEavesdropper`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_BB84ProtocolWithEavesdropper () : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_BB84ProtocolWithEavesdropper"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
